package com.lx.algorithm.recursion.class23;

import org.apache.poi.ss.formula.udf.UDFFinder;

import static com.lx.algorithm.radix.RadixSort.printArray;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-24 16:34:27
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-24     张李鑫                     1.0         1.0 Version
 */
public class SplitArr {
    /**
     * 给定一个正数数组arr，
     * 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
     * 返回：
     * 最接近的情况下，较小集合的累加和
     */

    public static int split(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }

        return process(arr, sum / 2, 0, 0);
    }

    private static int process(int[] arr, int target, int sum, int i) {
        if (sum > target) {
            return Integer.MIN_VALUE;
        }
        if (i == arr.length) {
            return sum;
        }

        int p1 = process(arr, target, sum + arr[i], i + 1);
        int p = process(arr, target, sum, i + 1);
        return Math.max(p1, p);
    }


    public static int dpII(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        sum /= 2;
        int[][] dp = new int[sum + 1][arr.length + 1];
        for (int i = sum; i >= 0; i--) {
            dp[i][arr.length] = i;
            for (int j = arr.length - 1; j >= 0; j--) {
                int p1 = i + arr[j] > sum ? 0 : dp[i + arr[j]][j + 1];
                int p2 = dp[i][j + 1];
                dp[i][j] = Math.max(p1, p2);
            }
        }

        return dp[0][0];
    }

    public static int dp(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        sum /= 2;
        int N = arr.length;
        int[][] dp = new int[N + 1][sum + 1];
        for (int i = N - 1; i >= 0; i--) {
            for (int rest = 0; rest <= sum; rest++) {
                // 可能性1，不使用arr[i]
                int p1 = dp[i + 1][rest];
                // 可能性2，要使用arr[i]
                int p2 = 0;
                if (arr[i] <= rest) {
                    p2 = arr[i] + dp[i + 1][rest - arr[i]];
                }
                dp[i][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][sum];
    }
    public static int[] randomArray(int len, int value) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * value);
        }
        return arr;
    }


    public static void main(String[] args) {
        int maxLen = 20;
        int maxValue = 50;
        int testTime = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * maxLen);
            int[] arr = randomArray(len, maxValue);
            int ans1 = dp(arr);
            int ans2 = dpII(arr);
            if (ans1 != ans2) {
                printArray(arr);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
